package algorithm.array;

/**
 * 【二分法】
 * leetcode : https://leetcode.com/problems/search-insert-position/description/
 * Difficulty : Easy
 *
 * 给一个有序数列，和一个数字，找到该数字在其中的插入序列
 * 举栗：
 * Input : [1,3,5,6], 5
 * Output : 2
 *
 * Input : [1,3,5,6], 2
 * Output : 1
 *
 * Input : [1,3,5,6], 7
 * Output : 4
 *
 * Input : [1,3,5,6], 0
 * Output : 0
 *
 * @Author Antony
 * @Since 2018/7/10 19:45
 */
public class SearchInsertPosition {

    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,6,7,9};
        int val = 5;
        System.out.println(searchInsert_binarySearch(arr, val));
    }


    /**
     * (beats 100.0% 3ms) 然而也是3ms
     * 简单循环
     * 时间复杂度最好O(1) 最差O(N) ，平均来看是O(N/2)
     * 不稳定，完全看 target在nums所处的位置
     */
    public static int searchInsert_loop(int[] nums, int target) {
        for(int i=0; i<nums.length; i++){
            if(nums[i] >= target){
                return i;
            }
        }
        // 最后如果都没找到，那就返回length 也就是末尾索引+1
        return nums.length;
    }


    /**
     * 二分法, 时间复杂度 O(logN)
     * (beats 100.0% - 3ms)
     * 注意是返回左边的那个索引值
     * （和二分查找还不一样，因为target可能不在数组中，但要求找到大于target的前一个位置）
     */
    public static int searchInsert_binarySearch(int[] nums, int target) {
        int left=0;
        int right = nums.length;
        int mid;
        while(left < right){
            mid = (left+right)/2;
            if (nums[mid]==target) return mid;  //先判断相等的情况,符合直接返回
            if(nums[mid] > target){
                right = mid;
            }else {
                //nums[mid] <= target 的情况
                left = mid+1;   //+1 防止死循环
            }
        }

        return left;
    }
}
